\line{\bf TRIVIA HUNT ANSWERS\hfil CS304, January 1987}
\bigskip
\font\eightrm=cmr8
\font\eightsy=cmsy8
\font\eighttt=cmtt8
\def\ans#1\!{\par\nobreak\medskip{\baselineskip=9pt\noindent\eightrm#1\par}}

\newcount\n
\def\\{\medbreak
\advance\n by 1 \item{\bf\number\n.}}
\def\=#1!{{\unskip\nobreak\hfil\penalty50\hskip2em\hbox{}\nobreak
 \hfil\sl#1\/\parfillskip=0pt\finalhyphendemerits=0\par}}

\\Who taught this course in 1971? In what room did it meet? What color are
the walls and doors of that room painted now?\=15 points each!
\ans Prof. Floyd taught CS204, Problem Seminar, in autumn quarter 1971--1972.
The room was Math 380-D, according to the Time Schedule [courtesy of
Stanford Editions and Publications]. The doors are stained brown;
the walls are covered with wallpaper: white in front, beige at the sides,
brown at the back. Stanford Maps and Records has no record of changes
since 1971; floorplans dated 1971 show the room as it now stands.
(When Knuth posed this problem, he was thinking of room 204 in Polya Hall,
where he taught the class some years later; that room has off-white painted
walls and dark blue doors.)
Some teams interviewed Floyd and Martin Frost (who
was one of the students in the course that quarter), but neither Floyd nor Frost
could remember whether the class was actually held in that room.\!

\\Who received the first two PhD's in Mathematics from Stanford?\=10 points each!
In what years did they finish their work?\=10 points each!
\ans William Albert Manning received the first, on May 18, 1904, according
to the 13th commencement program. Frank Clark Hoyt received a PhD jointly
from Math and Physics on June 20, 1921; this may qualify although the title
was definitely physics. Another such was awarded to George Russell Harrison
in 1922. But according to the reference book Stanford Dissertations (call
number AS36.S7), and according to a definitive-looking list in the math
library compiled by Prof.~Bacon in 1972, the second math PhD was completed
by Vern James (a student of Manning) in 1927.\!

\\Who received the first two PhD's
 in Computer Science from Stanford?\=5 points each!
In what year did they finish their work?\=5 points!
\ans William Marshall McKeeman and Dabbal Rajagopal Reddy completed their
theses in August, 1966 and their degrees were awarded in September of that
year. They are listed under `Computer Science' in the 1967
commencement program. Previous students who received PhD's in the Computer
Science Division of the Mathematics Department (Causey, Grace, Moler,
and Rudin) were listed under `Mathematics' in the commencement programs;
there was not as yet a Computer Science department.\!

\\What was the title of John McCarthy's PhD thesis?\=10 points!
How many pages long was it?\=10 points!
\ans Projection Operators and Partial Differential Equations.
Princeton University, 1951. 28 pages. [Reference:
Dissertation Abstracts 15 (1955), p.~601.] \ However, somebody had a friend
look up the thesis in Harvey Mudd library at Princeton, and it really
was only 27 pages long.\!

\\When did Gene Golub celebrate his 13th birthday?\=8 points!
\ans Gene was born on February 29, 1932, so his 13th birthday was
February 29, 1984; several students (e.g., Schaffer, Weening) remember
the party. He also celebrated age 13 somewhere near February 28 or March 1,
1945, when his bar mitzvah took place.\!

\\Of what journal is Leo Guibas the problem section editor?\=12 points!
\ans The Journal of Algorithms. [Reference: Inside front cover of any issue.]\!

\\Give the titles, co-authors, and years of publication of each book
by Jeff Ullman.\=4 points each!
\ans The following are in the card catalog (and they are also known to `Socrates'):
1.~(with Hopcroft) Formal Languages and their Relation to Automata, 1969.
2.~(with Aho) Theory of Parsing, Translation, and Compiling, vol.~1, 1972.
3.~(with Aho) Theory of Parsing, Translation, and Compiling, vol.~2, 1973.
4.~(with Aho and Hopcroft) Design and Analysis of Computer Algorithms, 1974.
5.~Fundamental Concepts of Programming Systems, 1976.
6.~(with Aho) Principles of Compiler Design, 1977.
7.~(with Hopcroft) Introduction to Automata Theory, Languages,
 and Computation, 1979.
8.~Principles of Database Systems, 1979.
9.~(with Aho and Hopcroft) Data Structures and Algorithms, 1983.
10.~Principles of Database Systems, 2nd edition, 1983.
11.~Computational Aspects of VLSI, 1984.
12.~(with Aho and Sethi) Compilers: Principles, Techniques, and Tools, 1986.
His vita also lists books scheduled to appear:
13.~(with Goldschlager and Mayr) Theory of Parallel Computation, 1987.
14.~Database and Knowledge-Base Systems, 1988.
15.~(with Aho) Principles of Computer Science, 1988.\!

\\What was Don Knuth's first scientific publication?\=10 points!
\ans The Potrzebie System of Weights and Measures, MAD magazine 33
 (June 1957), 36--37. [Reference: Knuth's vita.]\!

\\What faculty member in our department wrote a PhD thesis about game theory?
\=20 points!
\ans Nils John Nilsson, An application of the theory of games to radar
detection problems (EE, 1958). Found in main card catalog and elsewhere.\!

\\Which faculty members in our department had thesis advisors who have
won the ACM Turing award? \=20 points for each correct triple (faculty name,
advisor name, year of Turing award)!
\ans(Feigenbaum, Simon, 1975); (Guibas, Knuth, 1974); (Gupta, Newell, 1975);
(Manna, Perlis, 1966); (Manna, Floyd, 1978); (Nelson, Tarjan, 1986);
(Pratt, Knuth, 1974); (Rosenbloom, Newell, 1975); (Waldinger, Simon, 1975).
[Personal communications; the Turing winners are listed in CACM, January 83.]\!
% Binford's advisor was at Wisconsin
% Buchanan's was Gerald Massey at Michigan, now at Pitt
% Cheriton's was Michael Malcolm
% Feigenbaum's was Herb Simon*
% Genesereth's was Joel Moses informally(?) but somebody at Harvard officially
% Golub's was at Illinois
% Guibas's was Knuth*
% Gupta's was Newell* and somebody else, but this counts
% Hennessy's was at Stony Brook, Richard Kieburtz
% Katevenis's was probably not a winner
% Lantz's was Feldman
% Latombe's was in Grenoble
% Manna's was Floyd* and Perlis*
% Mayr's was M Paul
% Oliger's was in Sweden
% Papa's was Stieglitz
% Pratt's was Knuth*
% Rosenbloom's was Newell*
% Shoham's was McDermott
% Ullman's was at Princeton EE, Archie McKellar officially signed,
%  Art Bernstein officially advised earlier, Bob Chien (Yorktown) really advised
% Wiederhold's was Starkweather at UCSF
% Winograd's was Papert
% Turing winners were:
% Perlis 66, Wilkes 67, Hamming 68, Minsky 69, Wilkinson 70, McCarthy 71,
% Dijkstra 72, Bachman 73, Knuth 74, Newell&Simon 75, Rabin&Scott 76,
% Backus 77, Floyd 78, Iverson 79, Hoare 80, Codd 81, Cook 82,
% Thompson&Ritchie 83, Wirth 84, Karp 85, Hopcroft&Tarjan 86

\\Identify the author and source of the following quotations:\=10 points for
each author!\=15 points for each source!
\vskip-6pt
\itemitem{a.}Right as a serpent hit hym under floures\hfil\break
Til he may seen his tyme for to byte \dots
\ans Geoffrey Chaucer, The Squieres Tale [part of his Canterbury
Tales], lines 512--513.\!
\smallskip
\itemitem{b.}The upper pointer is stepped down, and proceeds on its downward scan
of the data. When it finds an item with key lower than the bound, this item is
copied into the locations referred to by the lower pointer. The lower
pointer is then stepped up, and the process is repeated until both pointers
are referring to the same item.
\ans C. A. R. Hoare, ``Quicksort,'' Computer Journal 5 (1982), p.~13.\!
\smallskip
\itemitem{c.}The most valuable acquisitions in a scientific or technical
education are the general-purpose mental tools which remain serviceable
for a lifetime.  I rate natural language and mathematics as the most
important of these tools, and computer science as a third.
\ans George E. Forsythe, ``What to do till the computer scientist comes,''
American Math Monthly 75 (1968), p.~456; quoted by Knuth in CACM 15 (1972),
p.~722.\!

\\What were the titles and dates of Stanford CS reports number 1
 and number 1000? Of Stanford AI~memo number 1? \=5 points each!
Were any of these three subsequently published in journals?
\=10 points for each journal citation!
\ans CS 1: Primal partition programming for block diagonal matrices,
 by J.~B. Rosen, November 8, 1963;
 published in Numerische Mathematik 6 (1964), 250--260. \quad
 CS 1000: Implementation of logical query languages for databases,
 by J.~D. Ullman, May 1984;
 published in ACM Transactions on Databases 10 (1985), 289-321.
 (Also in the supplement to the ACM-SIGMOD 1985 conference proceedings,
 pp.~1--17, where it was an invited paper.) \quad
 AIM 1: Predicate calculus with `undefined' as a truth value, John
 McCarthy, March 22, 1963; never published.\!

\\What integer number does the bit pattern 101011100010111000101110001011100011
represent in a
DEC-2060 computer?\=3 points for the correct answer, in decimal notation!
What floating-point number does it represent?\=7 points for the correct
answer, in decimal notation!
\ans The integer is {\eightsy\char0}21963283741, and the floating-point number
is {\eightsy\char0}2.1963284E+10, according to the `{\eighttt ddt}' program.
The latter represents {\eightsy\char0}21963283712\thinspace{\eightsy\char6}%
\thinspace128. (This and its negative are the only self-referential numbers
on the machine!)\!

\\Where did Seidel publish his method for solving linear systems by iteration?
\=10 points for correct reference, plus 15 points for copy of first page!
What was his full name? What were the dates of his birth and death?
\=7 points each!
\ans ``\"Uber ein Verfahren, die Gleichungen, auf welche die Methode der
kleinsten Quadrate f\"uhrt, sowie line\"are Gleichungen \"uberhaupt, durch
successive Ann\"aherun aufzul\"osen,'' in Abh. der II.~Classe der k.~bayerischen
Ak.~d.~Wiss.\ [that's the proceedings of the math-physics section of the
Royal Bavarian Academy of Sciences], vol.~11, part~3 (Munich, 1874), 81--103.
He was Philipp Ludwig von Seidel, according to Meyer's Enzyklop\"adisches
Lexikon and Scribner's Dictionary of Scientific Biography;
or Philipp Ludwig Seidel according to Poggendorf's Handw\"orterbuch;
both sources give birth date 24 Oct 1821 in Zweibr\"ucken, death date
13 Aug 1896 in Munich.\!


\\What is the number of the patent on the ENIAC?\=10 points!
How many claims did it have?\=10 points!
When was it filed, and when was it awarded?\=10 points!
When was it invalidated?\=15 points!
\ans Patent number 3,120,606. Filed 26 Jun 1947, awarded 4 Feb 1964(!).
148 claims. Invalidated 19 Oct 1973. [US Gov't Patent Office Official
Gazette 799 (February 1964); Annals of the History of Computing 3 (1981), 389;
US Patents Quarterly 180 (1974), 673--773.]\!

\\What city has been the site of both a STOC and a FOCS conference, since 1976?
\=15 points!
\ans Providence, Rhode Island, was STOC 85 and FOCS 77. [See the conference
proceedings, or CACM calendar of events, or Directory of Published Proceedings.]
Incidentally, Berkeley was STOC 86 and FOCS 75.\!

\\Find all journal articles published in 1982 whose title contains the
word `multigraphs'.\=10 points for each correct citation, plus 5 points
for each copy of the first page!
\ans 1.~Read and Robinson, Enumeration of labelled multigraphs by
degree parities, Discrete Math 42 (1982), 99--105. \
2.~Exoo and Harary, The smallest cubic multigraphs with prescribed
bipartite, block, Hamiltonian and planar properties, Indian J. Pure and
Applied Math 13 (1982), 309--312. \
3.~Gabow and Kariv, Algorithms for edge coloring bipartite graphs and
multigraphs, SIAM J. Computing 11 (1982), 117--129. \
4.~Taqqu and Goldberg, Regular multigraphs and their application to the
Monte Carlo evaluation of moments of non-linear functions of Gaussian
random variables, Stochastic Proc.~and their Applications 13 (1982),
121--138. [The first three are in the CompuMath subset of Science Citation
Index, but the last is only in the full index!]\!

\\The fundamental reference to the theory of multigrades is a book
by Albert Gloden called {\sl Mehrgradige Gleichungen\/} published in
the 40s. Find a review of this book in English.\=10 points for a xerox copy!
Find all references to this book made in scientific papers since 1976.
\=15 points each!
\ans Reviewed by D. H. Lehmer in Math Reviews 8 (1947), 441. Referred to
by E.~M. Wright, ``Tarry-Escott and the easier Waring problems,''
 J. f\"ur die reine und angewandte Math 311 (1979), 170--173.
 Also referred to by G. Myerson, ``How small can a sum of roots of unity be?''
 American Math Monthly 93 (1986), 457--459.\!

\\The longest known multigrades were first published in 1942, in a journal
called {\sl Gazeta Matematica}. What university libraries in the United States
contain the 1942 issue of that journal?\=10 points each!
\ans According to the Union List of Serials (1943), the only libraries
at that time were at the following universities: Brown, Chicago, Columbia,
Harvard. However, a check at Brown revealed that issues were not received
between 1940 and 1946. Other libraries may have acquired back issues since
then; this question is not resolved. Full credit was given for answers that
believed the Union List of Serials.\!

\\Find the longest words in the English language with the following
respective properties: (1)~All the letters are distinct (e.g.,
{\tt absorptively}). (2)~The word is a palindrome (e.g., {\tt madam}).
(3)~The letters of the word are sorted in nondecreasing order
(e.g., {\tt accept}). (4)~The letters of the word are sorted in
nonincreasing order (e.g., {\tt rookie}). (5)~The letters all appear
on the upper row of a typewriter keyboard (e.g., {\tt typewriter}).
Note: If your words are not commonly known, you must state their meaning and
give the name of a standard English dictionary that lists them.
\=12 points for each category, provided that no longer word
has been found by other teams!
\ans (1)~{\eighttt dermatoglyphics}, skin patterns. \
(2)~{\eighttt kinnikinnik} [Webster's 3rd], `a mixture of dried leaves
and bark and sometimes tobacco smoked by the Indians and pioneers
esp.~in the Ohio valley'. Next in line were {\eighttt malayalam}, a
Dravidian language related to Tamil [Guinness Book of Records], and
{\eighttt redivider}. \
(3)~{\eighttt aegilops}, an ulcer in the inner corner of the eye, also
a genus of grasses. \
(4)~{\eighttt spoonfeed}. Next is {\eighttt spoonfed}; then {\eighttt
wronged} and {\eighttt sponged} and some less common words. \
(5)~{\eighttt prettypretty} [Century Dictionary, 1914], `a knickknack'.
Next is {\eighttt rupturewort}, a European plant of genus Hernaria.
The book Language on Vacation by Dmitri Borgmann (1965) has more
info on questions like this. Some noted that the longest words satisfying
all five criteria simultaneously are `{\eighttt I}' and
`{\eighttt O}'.\!

\\What are synonyms of `{\tt cretinous}' in hackerese?\=5 points for each
documented answer!
\ans 
{\eighttt bagbiting},
{\eighttt barfulous},
{\eighttt barfucious},
{\eighttt bletcherous},
{\eighttt brain-damaged},
{\eighttt chomping},
{\eighttt demented},
{\eighttt losing}.
[The Hacker's Dictionary, by Steele et al.~(1983), pp.~28, 29, 36, 49.]\!

\\List all computers at Stanford that run the TOPS-20 operating system,
and tell in what building they are located.\=4 points for each correct
name and 6 points for each correct location!
\ans \kern-1ptVarious `host' commands identify them as:
{\eighttt score},
{\eighttt sushi}, and
{\eighttt truffle} in Margaret Jacks Hall;
{\eighttt lear},
{\eighttt othello},
{\eighttt hamlet}, and
{\eighttt macbeth} (aka {\eighttt lots-a} thru {\eighttt lots-d}) in CERAS;
{\eighttt how} and
{\eighttt why} in the Business School;
{\eighttt sumex} and
{\eighttt tiny} in the Medical School;
{\eighttt sierra} in Durand;
{\eighttt turing} (aka {\eighttt csli}) in Pine Hall.
There's also `{\eighttt panda}' at Mark Crispin's home; this may qualify
as `at Stanford' in some loose sense.\!

\\Where is it possible to see a life-size painting of Leland Stanford, Jr.,
at age~15?
Who was the artist? When was it painted?\=8 points each!
\ans In the Stanford Museum (room 7), painted by Felix Chary of Paris in 1884.\!

\\In what year was Margaret Jacks born?\=5 points!
What college did she attend?\=15 points!
What was her middle name?\=20 points!
What is the connection between her name and a popular food item?\=20 points!
\ans Her portrait at the entrance to Margaret Jacks Hall says that she
lived 1875--1962. She went to Radcliffe, according to the speech by Paul
Hanna when the building was dedicated. (This reference can be found in
Campus Report; it's cited under her name
in the Stanford Archives.) According to the biography of her father
David Jacks, by Arthur Bester, her middle name was Anna. [This can also
be found in her obituary, Calif.~Hist.~Quarterly 41 (1962), 367.]
According to the Monterey Peninsula Herald, 10 Nov 1982, page 34, Monterey
Jack cheese is named after her father, David Jacks, who produced the cheese
on his Carmel Valley Dairy Ranch and distributed it throughout California
under the name Jacks Monterey Cheese. [Webster's and other dictionaries
are not aware of the derivation of this word, nor are standard reference
books on cheese.]\!

\\What company was co-founded by Fletcher Jones?\=10 points!
 What is his connection with our department?\=10 points!
\ans He co-founded Computer Sciences Corporation about 1959; this was the first
(or nearly first) software company. He established the Jones Foundation
before his death in a private plane crash in 1972. That Foundation
endowed the first chair in our department in 1977. [Reference:
Endowed professorships at Stanford; or New York Times 9 Nov 1972, p.~50.]\!

\\What is the origin of the LISP terms `{\tt car}' and `{\tt cdr}'?\=10 points!
\ans This terminology comes from the IBM 704. It means the `contents of address
field of register' (the rightmost 15 bits) and `contents of decrement
field of a register' (the rightmost 15 of the leftmost 18); a `register'
at that time meant a memory word. The original LISP software stored
pointers there.  McCarthy alludes to this origin in his fundamental paper
``Recursive functions of symbolic expressions,''
CACM 3 (1960), p.~182. An explicit explanation appears in his paper on the
history of LISP, in the book History of Programming Languages edited by
Wexelblatt (1981), p.~175.\!

\bigskip\bigskip
\noindent {\bf Scores:}

\def\tbox#1{\omit\hidewidth\quad\vbox{\halign{##\hfil\cr#1\crcr}}\hidewidth}
\vbox{\tabskip=0pt plus 100pt
\halign to\hsize{#\hfil\quad&&\hfil#\cr
Problem&
\tbox{David S\cr Martin R\cr Ramin Z\cr Carlos S}&
\tbox{Derrick B\cr Scott S\cr Jack S\cr Michael W}&
\tbox{Rohit C\cr Kelly R}&
\tbox{Inderpal M\cr Hakan J}&
\tbox{Marcia D\cr David J\cr Liz W\cr Dave M}&
\tbox{Tom F\cr Barry H\cr Tom H\cr Alex W}\cr
\noalign{\smallskip}
1&	45&	44&	50&	30&	53&	61\cr
2&	40&	30&	0&	34&	20&	40\cr
3&	20&	20&	10&	20&	25&	20\cr
4&	20&	30&	10&	0&	20&	20\cr
5&	10&	8&	8&	8&	8&	10\cr
6&	12&	10&	0&	0&	13&	13\cr
7&	43&	51&	44&	52&	46&	54\cr
8&	10&	10&	3&	5&	15&	10\cr
9&	20&	19&	0&	0&	20&	20\cr
10&	85&	100&	60&	45&	150&	195\cr
11&	50&	0&	25&	50&	55&	80\cr
12&	35&	34&	25&	34&	35&	34\cr
13&	0&	9&	3&	11&	11&	9\cr
14&	35&	36&	31&	26&	36&	45\cr
15&	45&	45&	34&	35&	46&	45\cr
16&	15&	15&	15&	15&	15&	15\cr
17&	45&	65&	40&	45&	45&	45\cr
18&	38&	39&	24&	10&	39&	39\cr
19&	40&	0&	40&	40&	40&	40\cr
20&	0&	40&	0&	12&	38&	55\cr
21&	25&	20&	0&	20&	35&	42\cr
22&	120&	120&	130&	80&	124&	124\cr
23&	8&	27&	24&	24&	20&	24\cr
24&	30&	70&	0&	0&	50&	60\cr
25&	20&	20&	10&	20&	25&	20\cr
26&	10&	10&	5&	5&	10&	10\cr
\noalign{\smallskip}
Totals&	821&	872&	591&	621&	994&	1130\cr
}}

\bye